class Solution {
    public int deleteAndEarn(int[] nums) {
        // arr[i]表示i这个数出现的总和值
        // 相当于是i位置有arr[i]的钱
        int n = 10001; // 原数组值最大的值
        int[] arr = new int[n];

        // 将原数组转换为打家劫舍的数组
        for (int x : nums) {
            arr[x] += x;
        }

        // 对arr数组进行一次打家劫舍的操作
        // 创建dp表、初始化、填表、返回值
        int[] f = new int[n];
        int[] g = new int[n];

        // 不一定要从原始数组最小的位置开始
        // 可以直接从新数组的起始位置开始
        f[0] = arr[0];

        for (int i = 1; i < n; i++) {
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }

        return Math.max(f[n-1], g[n-1]);
    }
}